package com.zjj.algorithm.learning.leetcode.tree;

import java.util.Stack;

/**
 * @author zjj_admin
 * @date 2022/11/23 11:29
 */
public class DeleteLeavesWithGivenValue {

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(2);
        TreeNode node7 = new TreeNode(2);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node6.left = node7;

        TreeNode node = removeLeafNodes(node1, 2);
        System.out.println("node = " + node);


    }


    /**
     * 递归思想
     * <p>
     * 时间 0 ms 击败 100% 内存 41.4 MB 击败 7.91%
     *
     * @param root
     * @param target
     * @return
     */
    public static TreeNode removeLeafNodes(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        //依次递归调用左右叶子节点
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);
        //当叶子节点满足条件时，就直接返回 null
        if (root.val == target && root.left == null && root.right == null) {
            return null;
        }
        return root;
    }
}
